/*************************************************************************
> File Name: heap_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-21 10:36:36
> Description: 堆排序
************************************************************************/

#include <stdio.h>
#include "general.h"

int heapSort(int arr[], int size);
static int buildMaxHeap(int arr[], int size);
static void maxHeapify(int arr[], int start, int end);

int main(int argc, char const *argv[])
{

    int arr[] = {9, 4, 2, 7, 5, 1, 8, 3, 6, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, size);
    heapSort(arr, size);
    printf("Sorted array: \n");
    printArr(arr, size);
    return 0;
}
int heapSort(int arr[], int size)
{
    int i = 0;
    buildMaxHeap(arr, size); // 初始化堆栈
    for (i = size - 1; i > 0; i--)
    {
        swap(&arr[0], &arr[i]);
        maxHeapify(arr, 0, i - 1);
    }
}
static void maxHeapify(int arr[], int start, int end)
{
    int dad = start;
    int son = dad * 2 + 1; // 默认左节点
    while (son <= end)
    {
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 右节点更大
        {
            son++;
        }
        if (arr[dad] > arr[son]) // 父节点比子节点大;
        {
            return;
        }
        else
        {
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
static int buildMaxHeap(int arr[], int size)
{
    int i = 0;
    for (i = size / 2 - 1; i >= 0; i--) // 从size/2-1的父节点开始整理
    {
        maxHeapify(arr, 0, size - 1);
    }
}
